#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int Getrand(vector<int>& nums, int l, int r)
    {
        srand(time(nullptr));
        return nums[rand() % (r - l + 1) + l];
    }
    void quilksort(vector<int>& nums, int l, int r, int k)
    {
        if (l > r)
            return;
        int key = Getrand(nums, l, r);
        int left = l - 1; int right = r + 1; int cur = l;
        while (cur < right)
        {
            if (nums[cur] > key)   swap(nums[cur], nums[--right]);
            else if (nums[cur] < key)  swap(nums[cur++], nums[++left]);
            else    cur++;
        }
        int a = left - l + 1; int b = right - left - 1;
        if (a > k) quilksort(nums, l, left, k);
        else if (a + b >= k) return;
        else    quilksort(nums, right, r, k - a - b);
    }

    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        int l = 0; int r = stock.size() - 1;
        quilksort(stock, l, r, cnt);
        vector<int> sum;
        while (cnt--)
        {
            sum.push_back(stock[cnt]);
        }
        return sum;
    }
};

class Solution {
public:
    int Getrand(vector<int>& nums, int l, int r)
    {
        srand(time(nullptr));
        return nums[rand() % (r - l + 1) + l];
    }

    int quilksort(vector<int>& nums, int l, int r, int k)
    {
        if (l == r)
            return nums[l];
        int key = Getrand(nums, l, r);
        int left = l - 1; int right = r + 1; int cur = l;
        while (cur < right)
        {
            if (nums[cur] > key)   swap(nums[cur], nums[--right]);
            else if (nums[cur] < key)  swap(nums[cur++], nums[++left]);
            else    cur++;
        }
        if (r - right + 1 >= k) return quilksort(nums, right, r, k);
        else if (r - left >= k) return nums[left + 1];
        else   return quilksort(nums, l, left, k - (r - left));

    }

    int findKthLargest(vector<int>& nums, int k) {
        int l = 0; int r = nums.size() - 1;
        return quilksort(nums, l, r, k);
    }
};

int main()
{
    return 0;
}